/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月06日
*   描    述：
*
================================================================*/

/*
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 * 示例 1：
 *   输入：nums = [1,2,0]
 *   输出：3
 *
 * 示例 2：
 *   输入：nums = [3,4,-1,1]
 *   输出：2
 *
 * 示例 3：
 *   输入：nums = [7,8,9,11,12]
 *   输出：1
 *
 * 提示：
 *   1 <= nums.length <= 5 * 105
 *   -231 <= nums[i] <= 231 - 1
 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int firstMissingPositive(int *nums, int numsSize) {
  uint8_t *tags = (uint8_t *)malloc(numsSize + 1);
  int i = 0;
  memset(tags, 0, numsSize + 1);
  for (i = 0; i < numsSize; i++) {
    if (nums[i] <= 0 || nums[i] > numsSize) {
      continue;
    }
    tags[nums[i]] = 1;
  }

  for (i = 1; i < numsSize + 1; i++) {
    if (tags[i] == 0) break;
  }
  return i;
}

int main() {
  int nums[] = {0, 1, 2};
  int ret = firstMissingPositive(nums, sizeof(nums) / sizeof(nums[0]));
  printf("%d\n", ret);
  return 0;
}